병합 정렬

병합정렬은 퀵정렬과 대표되는 O(nlogn)의 시간복잡도를 가진 정렬로 최악에 O(n2)의 시간복잡도를 가지는 퀵정렬과 달리 모든 경우의 O(nlogn)의 시간복잡도를 가지는 정렬이다. 또한 퀵정렬이 분할해 나가면서 정렬하는 방식이었다면 병합정렬은 모두 분할한 뒤 그 결과를 합치는 방법으로 약간의 차이가 있다. 병합정렬의 단점은 병합된 결과를 저장하기 위한 배열이 필요하기 때문에 메모리를 많이 차지할 수 있다.

병합정렬을 하는 과정은 배열을 mid를 기준으로 크기가 1인 배열이 될 때 까지 나누게 된다. 왼쪽 오른쪽으로 나눈 결과는 정렬 과정을 거치며 합쳐지고 이 과정을 반복하여 정렬을 수행해 나간다.

나뉘어진 원소를 합치면서 정렬하는 과정은 두 배열의 원소의 크기를 비교해나가며 작은 순서로 정렬된 결과 배열에 집어 넣는 것이다. {2,5} {4,6} 이라는 배열이 존재하면 각각 비교할 서로의 인덱스를 선언한다. 그리고 그 인덱스에 해당하는 아이템을 비교하고 더 작으면 결과 배열에 넣고 더 작았던 쪽 배열의 인덱스를 증가시킨다.

이 과정을 반복하고 마지막에 남은 원소들을 모두 끝에 넣어주게 되면 정렬된 결과가 나오게 된다. 이 과정이 반복되면서 정렬된 왼쪽, 오른쪽 배열들이 다시 합쳐지면서 정렬되어 최종으로 모두 정렬된 결과가 나오게 된다.

아래의 코드에서 MergeSort1은 결과를 저장하기 위해 배열을 선언한 것이고 MergeSort2는 배열 내에서 정렬을 수행한 코드이다.

MergeSort1

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<ctime>

using namespace std;

vector<int> Merge(vector<int> arr1, vector<int> arr2)
{
	vector<int> result;
	int arr1_index = 0;
	int arr2_index = 0;

	while (arr1_index < arr1.size() && arr2_index < arr2.size())
	{
		if (arr1[arr1_index] < arr2[arr2_index])
		{
			result.push_back(arr1[arr1_index]);
			arr1_index++;
		}
		else
		{
			result.push_back(arr2[arr2_index]);
			arr2_index++;
		}
	}

	while (arr1_index < arr1.size())
	{
		result.push_back(arr1[arr1_index]);
		arr1_index++;
	}
	while (arr2_index < arr2.size())
	{
		result.push_back(arr2[arr2_index]);
		arr2_index++;
	}

	return result;

}

vector<int> MergeSort(vector<int>& arr, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		vector<int> arr1 = MergeSort(arr, left, mid);
		vector<int> arr2 = MergeSort(arr, mid + 1, right);
		return Merge(arr1, arr2);
	}
	else
	{
		vector<int> temp;
		temp.push_back(arr[left]);
		return temp;
	}
}
void main()
{
	srand((unsigned int)time(NULL));

	vector<int> arr;
	for (int i = 0; i < 10; i++)
		arr.push_back(rand() % 100);

	vector<int> result = MergeSort(arr, 0, arr.size() - 1);

	for (int i = 0; i < 10; i++)
		printf("%d ", result[i]);
}

​ 정렬된 결과를 따로 리턴하는 병합 정렬

MergeSort2

#include<cstdio>
#include<vector>
#include<cstdlib>
#include<ctime>

using namespace std;

vector<int> arr;

void Merge(int left,int right)
{
	vector<int> result;
	int mid = (left + right) / 2;
	int arr1_index = left;
	int arr2_index = mid+1;

	while (arr1_index < mid+1 && arr2_index < right + 1)
	{
		if (arr[arr1_index] < arr[arr2_index])
		{
			result.push_back(arr[arr1_index]);
			arr1_index++;
		}
		else
		{
			result.push_back(arr[arr2_index]);
			arr2_index++;
		}
	}

	while (arr1_index < mid+1)
	{
		result.push_back(arr[arr1_index]);
		arr1_index++;
	}
	while (arr2_index < right + 1)
	{
		result.push_back(arr[arr2_index]);
		arr2_index++;
	}

	for (int i = 0; i < result.size(); i++)
	{
		arr[i + left] = result[i];
	}

}

void MergeSort(vector<int>& arr, int left, int right)
{
	if (left < right)
	{
		int mid = (left + right) / 2;
		MergeSort(arr, left, mid);
		MergeSort(arr, mid + 1, right);
		Merge(left, right);
	}
	
}
void main()
{
	srand((unsigned int)time(NULL));

	
	for (int i = 0; i < 10; i++)
		arr.push_back(rand() % 100);

	MergeSort(arr, 0, arr.size() - 1);

	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
}

​ 전역변수를 통해 전역범수 안에서 정렬을 수행하는 병합 정렬